package com.LeeCode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 最长合法子字符串的长度
 */

public class Code2781 {
    public static void main(String[] args) {

    }

    public int longestValidSubstring(String word, List<String> forbidden) {
        // 1. 预处理 forbidden 集合
        Set<String> forbiddenSet = new HashSet<>();
        int maxForbiddenLen = 0;
        for (String s : forbidden) {
            forbiddenSet.add(s); // 将 forbidden 字符串存入 HashSet 以便快速查找
            maxForbiddenLen = Math.max(maxForbiddenLen, s.length()); // 记录 forbidden 字符串的最大长度
        }

        int maxLen = 0; // 记录最长合法子字符串的长度
        int left = 0; // 滑动窗口的左边界

        // 2. 滑动窗口遍历 word
        for (int right = 0; right < word.length(); right++) {
            // 3. 检查以 right 结尾的所有可能非法子串
            // 只需要检查长度不超过 maxForbiddenLen 的子串
            // 从右往左检查
            for (int k = right; k >= left && k >= right - maxForbiddenLen + 1; k--) {
                String substring = word.substring(k, right + 1); // 当前子串
                if (forbiddenSet.contains(substring)) { // 如果子串非法
                    left = k + 1; // 移动左边界到非法子串的右侧
                    break; // 跳出检查，因为更短的子串不需要再检查
                }
            }
            // 4. 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1); // 当前窗口大小是 right - left + 1
        }

        return maxLen; // 返回最长合法子字符串的长度
    }

}
